home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Mindy / Mindy 1.2 - portable sources / interp / sym.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  6.4 KB  |  283 lines  |  [TEXT/ttxt]
  1. /**********************************************************************\
  2. *
  3. *  Copyright (c) 1994  Carnegie Mellon University
  4. *  All rights reserved.
  5. *  
  6. *  Use and copying of this software and preparation of derivative
  7. *  works based on this software are permitted, including commercial
  8. *  use, provided that the following conditions are observed:
  9. *  
  10. *  1. This copyright notice must be retained in full on any copies
  11. *     and on appropriate parts of any derivative works.
  12. *  2. Documentation (paper or online) accompanying any system that
  13. *     incorporates this software, or any part of it, must acknowledge
  14. *     the contribution of the Gwydion Project at Carnegie Mellon
  15. *     University.
  16. *  
  17. *  This software is made available "as is".  Neither the authors nor
  18. *  Carnegie Mellon University make any warranty about the software,
  19. *  its performance, or its conformity to any specification.
  20. *  
  21. *  Bug reports, questions, comments, and suggestions should be sent by
  22. *  E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  23. *
  24. ***********************************************************************
  25. *
  26. * $Header: sym.c,v 1.8 94/11/28 15:01:26 wlott Exp $
  27. *
  28. * This file implements symbols.
  29. *
  30. \**********************************************************************/
  31.  
  32. #include "../compat/std-c.h"
  33.  
  34. #include <ctype.h>
  35.  
  36. #include "mindy.h"
  37. #include "gc.h"
  38. #include "bool.h"
  39. #include "class.h"
  40. #include "obj.h"
  41. #include "coll.h"
  42. #include "str.h"
  43. #include "def.h"
  44. #include "list.h"
  45. #include "type.h"
  46. #include "print.h"
  47. #include "sym.h"
  48.  
  49. obj_t obj_SymbolClass = NULL;
  50.  
  51. struct symbol {
  52.     obj_t class;
  53.     obj_t name;
  54.     obj_t next;
  55.     unsigned hash;
  56. };
  57.  
  58. static struct symtable {
  59.     obj_t class;
  60.     int entries;
  61.     int threshold;
  62.     int length;
  63.     obj_t *table;
  64. } Symbols;
  65.  
  66. static unsigned hash_name(char *name)
  67. {
  68.     unsigned char *ptr;
  69.     unsigned hash = 0;
  70.  
  71.     for (ptr = (unsigned char *)name; *ptr; ptr++)
  72.     hash = ((hash<<5)|(hash>>27)) ^ (*ptr & ~('a'^'A'));
  73.  
  74.     return hash;
  75. }
  76.  
  77. static boolean same_name(char *name1, char *name2)
  78. {
  79.     char c1, c2;
  80.  
  81.     while (1) {
  82.     c1 = *name1++;
  83.     c2 = *name2++;
  84.     
  85.     if (c1) {
  86.         if ((isupper(c1) ? tolower(c1) : c1)
  87.         != (isupper(c2) ? tolower(c2) : c2))
  88.         return FALSE;
  89.     }
  90.     else if (c2)
  91.         return FALSE;
  92.     else
  93.         return TRUE;
  94.     }
  95. }
  96.  
  97. static void rehash_table(struct symtable *table)
  98. {
  99.     int new_length;
  100.     obj_t *new_table;
  101.     obj_t *ptr;
  102.     int i;
  103.  
  104.     if (table->length < 1024)
  105.     new_length = table->length << 1;
  106.     else
  107.     new_length = table->length + 1024;
  108.  
  109.     new_table = (obj_t *)malloc(sizeof(obj_t)*new_length);
  110.  
  111.     ptr = new_table;
  112.     for (i = 0; i < new_length; i++)
  113.     *ptr++ = obj_False;
  114.  
  115.     ptr = table->table;
  116.     for (i = 0; i < table->length; i++) {
  117.     obj_t sym, next;
  118.     for (sym = *ptr++; sym != obj_False; sym = next) {
  119.         int index = obj_ptr(struct symbol *, sym)->hash % new_length;
  120.         next = obj_ptr(struct symbol *, sym)->next;
  121.         obj_ptr(struct symbol *, sym)->next = new_table[index];
  122.         new_table[index] = sym;
  123.     }
  124.     }
  125.  
  126.     free(table->table);
  127.     table->table = new_table;
  128.     table->length = new_length;
  129.     table->threshold = (new_length * 3) / 2;
  130. }
  131.  
  132. static obj_t intern(char *name, struct symtable *table)
  133. {
  134.     unsigned hash = hash_name(name);
  135.     int index = hash % table->length;
  136.     obj_t sym;
  137.  
  138.     for (sym = table->table[index];
  139.      sym != obj_False;
  140.      sym = obj_ptr(struct symbol *, sym)->next) {
  141.     if (obj_ptr(struct symbol *, sym)->hash == hash) {
  142.         obj_t sym_name = obj_ptr(struct symbol *, sym)->name;
  143.         if (same_name(name, (char *)obj_ptr(struct string *, sym_name)->chars))
  144.         return sym;
  145.     }
  146.     }
  147.  
  148.     sym = alloc(table->class, sizeof(struct symbol));
  149.     obj_ptr(struct symbol *, sym)->name = make_byte_string(name);
  150.     obj_ptr(struct symbol *, sym)->next = table->table[index];
  151.     obj_ptr(struct symbol *, sym)->hash = hash;
  152.     table->table[index] = sym;
  153.     
  154.     table->entries++;
  155.     if (table->entries >= table->threshold)
  156.     rehash_table(table);
  157.  
  158.     return sym;
  159. }
  160.  
  161. obj_t symbol(char *name)
  162. {
  163.     return intern(name, &Symbols);
  164. }
  165.  
  166. char *sym_name(obj_t sym)
  167. {
  168.     obj_t string = obj_ptr(struct symbol *, sym)->name;
  169.  
  170.     return (char *)obj_ptr(struct string *, string)->chars;
  171. }
  172.  
  173. unsigned sym_hash(obj_t sym)
  174. {
  175.     return obj_ptr(struct symbol *, sym)->hash;
  176. }
  177.  
  178.  
  179.  
  180. /* Dylan functions. */
  181.  
  182. /* The following as methods only work on <byte-string>s */
  183.  
  184. static obj_t string_as_symbol(obj_t class, obj_t string)
  185. {
  186.     return symbol((char *)obj_ptr(struct string *, string)->chars);
  187. }
  188.  
  189. static obj_t symbol_as_string(obj_t class, obj_t symbol)
  190. {
  191.     return obj_ptr(struct symbol *, symbol)->name;
  192. }
  193.  
  194.  
  195. /* Printing. */
  196.  
  197. static void print_symbol(obj_t symbol)
  198. {
  199.     printf("#\"%s\"", sym_name(symbol));
  200. }
  201.  
  202.  
  203. /* GC stuff. */
  204.  
  205. static int scav_sym(struct object *o)
  206. {
  207.     struct symbol *sym = (struct symbol *)o;
  208.  
  209.     scavenge(&sym->name);
  210.     scavenge(&sym->next);
  211.  
  212.     return sizeof(struct symbol);
  213. }
  214.  
  215. static obj_t trans_sym(obj_t sym)
  216. {
  217.     return transport(sym, sizeof(struct symbol));
  218. }
  219.  
  220. static void scav_table(struct symtable *table)
  221. {
  222.     int i;
  223.     obj_t *ptr;
  224.  
  225.     scavenge(&table->class);
  226.     ptr = table->table;
  227.     for (i = 0; i < table->length; i++)
  228.     scavenge(ptr++);
  229. }
  230.  
  231. void scavenge_symbol_roots(void)
  232. {
  233.     scavenge(&obj_SymbolClass);
  234.     scav_table(&Symbols);
  235. }
  236.  
  237.  
  238. /* Init stuff. */
  239.  
  240. void make_sym_classes(void)
  241. {
  242.     obj_SymbolClass = make_builtin_class(scav_sym, trans_sym);
  243. }
  244.  
  245. static void init_table(struct symtable *table, obj_t class)
  246. {
  247.     obj_t *ptr;
  248.     int i;
  249.  
  250.     table->class = class;
  251.     table->entries = 0;
  252.     table->threshold = 96;
  253.     table->length = 64;
  254.     table->table = (obj_t *)malloc(sizeof(obj_t)*64);
  255.     ptr = table->table;
  256.     for (i = 0; i < 64; i++)
  257.     *ptr++ = obj_False;
  258. }
  259.  
  260. void init_symbol_tables(void)
  261. {
  262.     init_table(&Symbols, obj_SymbolClass);
  263. }
  264.  
  265. void init_sym_classes(void)
  266. {
  267.     init_builtin_class(obj_SymbolClass, "<symbol>", obj_ObjectClass, NULL);
  268.     def_printer(obj_SymbolClass, print_symbol);
  269. }
  270.  
  271. void init_sym_functions(void)
  272. {
  273.     define_method("as", list2(singleton(obj_SymbolClass), obj_ByteStringClass),
  274.           FALSE, obj_False, FALSE, obj_SymbolClass, string_as_symbol);
  275.     define_method("as", list2(singleton(obj_StringClass), obj_SymbolClass),
  276.           FALSE, obj_False, FALSE, obj_ByteStringClass,
  277.           symbol_as_string);
  278.     /* same method as above, only for singleton <byte-string> */
  279.     define_method("as", list2(singleton(obj_ByteStringClass), obj_SymbolClass),
  280.           FALSE, obj_False, FALSE, obj_ByteStringClass,
  281.           symbol_as_string);
  282. }
  283.